Artificial Intelligence 101

Update, October 2011: For a different take on the subject, Stanford University is offering an online Introduction to Artificial Intelligence class; the first video is available here.

part 1: what is intelligence?

When building an artificial something, it helps to know what the natural version of that something is. For example, when building a prosthetic leg, having an idea of what a natural leg is, what it is used for, how it interfaces with the rest of the body and so on is critical; without that information, the artificial version of a leg might have wheels or a knee that bends in all directions or so much mass that walking becomes impossible. There are details which are important to our purposes (such as the placement of the big toe, which is essential for balance), and details that are unimportant (like the exact number and placement of hairs on the leg) - and we need to figure out which of those details are important, to incorporate them into our artificial device.

However, "intelligence" is an abstract concept, not a concrete object like a leg. It cannot be weighed or measured with a ruler or touched. Instead we need to describe what we know about intelligence and how it is used. Moreover, we need to be able to evaluate our attempts at creating artificial intelligence, so that we can compare approaches, make improvements, and ultimately decide whether what we have made is indeed "intelligent".

Dictionary.com defines intelligence as

capacity for learning, reasoning, understanding, and similar forms of mental activity; aptitude in grasping truths, relationships, facts, meanings, etc...the faculty of understanding.

That's pretty broad, and it requires knowing what we mean by such words as learning, understanding, meaning, consciousness and so on - concepts that themselves are all interlinked with what we mean by intelligence in the first place. Marvin Minsky wrote in The Society of Mind that

it isn't wise to treat an old, vague word like "intelligence" as though it must define any definite thing. Instead of trying to say what such a word "means", it is better simply to try to explain how we use it.

Our minds contain processes that enable us to solve problems we consider difficult. "Intelligence" is our name for whichever of those processes we don't yet understand.

Neither of these definitions really helps us to decide if whatever artificial intelligence we make is actually "intelligent".

Each of us is conscious of our own intelligence, and we infer intelligence in other people based on our observations of their behavior and our past interactions. And it isn't only in other people that we observe intelligence; we see it in animals, too. Dogs can certainly exhibit intelligence, as any dog owner will tell you. Chimpanzees can learn to communicate with sign language. Dolphins are pretty darn smart. If animals can exhibit intelligence and some degree of consciousness, then this implies that there is nothing mysterious or magical about thought, consciousness, emotion, creativity, learning, empathy, or any of the qualities of the brain that we call "intelligence". Indeed, intelligence is rather common, in various forms and degrees - and there is nothing magical required to reproduce that in a machine.

So what would be a useful definition of intelligence, something we can use as a working model of thought for a machine?

It is probably counterproductive to define intelligence too narrowly. As early as 1958 is was predicted that "within ten years a digital computer will be the world's chess champion" - and on May 11, 1997, Deep Blue beat the reigning world chess champion, Garry Kasparov. Today, Kasparov is deeply involved in Russian politics, and Deep Blue ... can play chess.

Alan Turing proposed a test in which

a human judge engages in a natural language conversation with one human and one machine, each of which tries to appear human. All participants are placed in isolated locations. If the judge cannot reliably tell the machine from the human, the machine is said to have passed the test. In order to test the machine's intelligence rather than its ability to render words into audio, the conversation is limited to a text-only channel such as a computer keyboard and screen.

Anyone who has been fooled by a chatterbot, however briefly, would probably concede that Turing's test has likely been passed on numerous occasions - and dismissed as "not really artificial intelligence".

The challenges of playing chess at a world-class level or chatting over the internet do require intelligence in human beings, but defining such tests as indicative of intelligence in and of themselves is too narrow of a definition, and solving only those narrow problems doesn't tell us anything about the nature of intelligence in general. Within their very limited domains, they work fine - but take Deep Blue out of the 64-square universe of chess and it is lost.

In the late 1980s, researchers began to put forth the idea that in order to show true intelligence, the machine needed to have a body, to interact and deal with the real world. As Rodney Brooks said, Elephants don't play chess. It is the real world that presents the challenges for survival to an animal, and a choice made by that animal can mean the difference between reproducing and being something else's lunch. And if an artificial intelligence has a body and must deal with the real world, controlling itself and avoiding obstacles and so forth in real time, then its control system must be a more robust version of AI than is required to deal with any simulation.

In the real world, intelligence is a quality of the animal mind that allows it to make choices and perform actions that enable it in the short term to consume food and acquire the other necessities of life while avoiding lethal situations, and in the long term to survive enough short-term needs that it can live long enough to reproduce.

OK, so that definition is still pretty broad, but it's a good starting point: intelligence is the ability to make choices that enable survival.

A rock rolling down a mountainside cannot make choices - it simply moves where its own momentum, friction, and gravity dictate. A plant slowly twisting to track the sun isn't making any choices - it only points towards the strongest light as it is forced to by its own structure and the laws of Physics, and it would follow a more intense artificial light if one was present. When you burn your hand on a stove and your reflexes cause your arm to jerk away from the heat, you're not making a choice either - a direct connection in your neural wiring leads from your pain receptors to the spinal cord and back to the muscles of your arm, and the laws of Physics force the movement of your arm.

In the above examples, the action taken in response to a stimulus is completely dictated by the laws of Physics. Does that mean that the ability to make choices somehow exists outside of those physical laws? Do we need to invoke something supernatural in order to explain consciousness or intelligence or free will?

No, we don't. Everything that happens in this universe happens according to the laws of Physics, without exception, whether we realize it or not. Everything we do, every thought that we have, every choice we make, is dictated by the laws of Physics just like a falling rock's path.

So what is the qualitative difference between a falling rock and, for instance, me choosing which word to type next? From the perspective of the laws of Physics, there is no difference.

Layers of Abstraction and Emergent Properties

A proton is a proton is a proton. Every proton in the universe is exactly the same as all the others. The behavior of every proton is exactly the same as every other one. If a proton is removed from the nucleus of an atom, and immediately replaced with another proton, then the atom is exactly the same as it was before. There is no difference.

Likewise, every neutron is exactly the same as every other neutron, and every electron is exactly the same as every other electron. Each always follows the laws of Physics, in particular the conservation laws of mass/energy, momentum, angular momentum, and charge.

However, protons and neutrons and electrons do not exist in isolation. Each contributes to the electromagnetic field and gravitational field, each occupies some region of spacetime and each interacts with all the others.

When protons, neutrons, and electrons are proximal, then they combine with each other to form atoms - a positively charged nucleus containing protons and neutrons, and a negatively charged cloud of electrons bound to the nucleus through electromagnetism. The interaction of the electrons with each other gives certain regions of the atom that can combine with similar regions of other atoms, sharing electrons between the two atoms and forming a chemical bond. This allows molecules to form, and the interactions of molecules with each other gives us all of Chemistry. Specific patterns of molecules give us things like RNA and DNA and adenosine triphosphate and hemoglobin and ribosomes and all the other compounds necessary for life.

That falling rock is made of the same protons and neutrons and electrons as exist in your left hand. There is no difference whatsoever between a proton in that rock and a proton in a molecule of your hemoglobin, and those two protons could be exchanged without there being any difference to either the rock or your blood.

The building blocks are the same. The rules are the same. If there is no difference, then how come that rock and your left hand look different, behave differently, and have different capabilities?

The difference lies in the way that those fundamental building blocks are arranged. At a basic level, they are merely identical protons and neutrons and electrons, but go up a couple of levels of abstraction and they are arranged into different molecules with different behaviors. Each of those molecules still follows the laws of Physics exactly, but because of the way that the atoms are arranged in each, new properties of the molecule begin to appear.

A property like viscosity or temperature does not exist for an isolated atom, but go up one level of abstraction, where the fundamental building blocks combine to form molecules, and those properties emerge. Go up another level of abstraction, where the molecules form cells, and you get new properties emerging such as cell division. At still higher levels of abstraction, as cells combine and specialize to form a multicellular organism, we see still further properties emerging, like respiration and excretion. Go up another level of abstraction and still more properties emerge, such as the flight of a bumblebee. At a higher level of abstraction we see still more properties emerging, such as the density waves that occur in rush-hour traffic.

Likewise, a bit is a bit is a bit - to a computer, it doesn't matter whether that bit is stored within RAM or on a hard drive or a CD or is transmitted over the internet. It is either a logical 1 or a logical 0. By itself, a 1 or a 0 isn't particularly interesting. It is logically equivalent to a light switch on your wall - when it is a 0 the light is off and when it is a 1 the light is on. However, those ones and zeros can be combined, and new behaviors can emerge when we take them to a higher level of abstraction. For instance, two such bits can be combined in a digital logic gate, like a NAND gate. In a NAND gate, the output depends on the state of the two inputs: if both inputs are a one then the output will be a zero, and if either input is a zero then the output is a one.

This NAND gate might not seem particularly useful, by itself. However, by linking together NAND gates in a network we can create any digital circuit. These arrangements of NAND gates represent a new level of abstraction, and as such new properties emerge. Depending on the way that these gates are linked together, they can act as a group to form a frequency generator, or a flip-flop, or a binary adder, or a shift register, or a comparator, or a latch. These circuits can be optimized - they don't need to be made from NAND gates, although they could - and themselves combined in a new level of abstraction into such things as microprocessors and RAM and peripheral interface circuits. These have new capabilities which emerge, such as running a machine-language computer program.

The individual machine language that works for a particular microprocessor will not work for another microprocessor whose circuits are arranged differently. So, a higher level of abstraction is needed, where programs can be written in a common, higher-level language like C++, and then compiled into the appropriate lower level machine-language program. And once again, at this higher level of abstraction new capabilities emerge: operating systems, web browsers, games, spreadsheets, databases, file sharing, websites, search engines, blogs, and so forth.

One particular computer program can illustrate this point further. In 1970, John Conway proposed a game he called Life. In this game, a display grid is made up of pixels, each of which can be either ON or OFF. Each pixel has eight neighbors: above, below, left, right, and four diagonal neighbors. The rules are simple - if a pixel has fewer than two or more than three neighbors in the ON state, it goes OFF at the next clock cycle. If it has exactly three neighbors ON, then the next clock cycle it goes ON. And if it has exactly two neighbors ON, then it is unchanged on the next clock cycle. The behavior of the system is entirely dictated by the initial states of the pixels in the grid and by those simple rules.

Now, we take it up one level of abstraction, and observe the behavior of a group of pixels over many clock cycles. When the pixels are interacting with each other as a group, each affecting all its neighbors, we begin to see patterns emerge. One group of five ON pixels arranged in a particular way acts as a "glider", which re-forms the original five-pixel pattern four clock states later, shifted one pixel diagonally from the original position. Over time this glider acts like a photon, moving in a straight line at the "speed of light" for the simulated universe of the game, one diagonal pixel every four clock cycles. Other structures also become apparent, such as the Glider Gun (which produces gliders one after the other) or a Breeder (which creates a series of glider guns). Starting with a "universe" and applying simple rules at the lowest level of abstraction, we see higher-order behaviors and structures emerge as we observe higher levels of abstraction.

In all these examples, each time we look at a higher and higher level of abstraction, we find new properties emerging - each still following the laws of Physics, each property dependent upon the properties of lower levels of abstraction, and each property emerging only as those building blocks at lower levels combine to form a new structure with properties not possible at the lower level of abstraction.

And so it is with intelligence. The components that make up our brains, from the fundamental building blocks to the atoms and molecules and the neurons themselves, each follows simple rules ultimately dictated by the laws of Physics, but each exhibiting emergent behaviors as they are linked together in higher and higher levels of abstraction. The individual neuron by itself is not intelligent, but combine neurons together and they start to form functional groups. Each group is capable of performing some specific computational task, and each is, by itself, unintelligent. However, if we go up another level of abstraction, these functional groups combine and interact with each other and new properties emerge, such as controlling your heartbeat. And as we continue to increase the level of abstraction and combine less-capable structures together in different ways, still more new properties begin to emerge, like the fight or flight response.

So we can now say this about intelligence in general: functional groups of neurons, each unintelligent by itself, combine with each other to introduce new capabilities at a higher level of abstraction - and taken as a group, these emergent properties are what we call intelligence:

Intelligence is an emergent property of the combination of unintelligent functional groups.

This doesn't mean that we can create these functional groups and simply stir them together in a pot and pow intelligence appears like magic. There are an infinite number of possible functional groups, and an infinite number of ways to combine these lower-level functions into higher levels of abstraction, and we don't have enough time to try them all.

Fortunately, we don't have to try them all. No animal has to try every possible combination of neurons in its brain in order to exhibit intelligence - the physical structure of the animal's body, with its inherent capabilities and long-term stability, forces the formation of long-term structures of neurons specific to its body. The connections between these structures are themselves other neural structures, which can be used in the same way as the lower-level structures but which perform higher order tasks. The structures are not randomly connected in all their infinite number of possible combinations; those which are useful are retained, and those which are not useful are not retained.

feedback

So, back to the development of our definition: how do we go from combination of simple unintelligent structures into higher levels of abstraction, to the ability to make choices?

The decisions an animal makes have immediate consequences. Imagine a pack of wolves hunting a deer. As the deer runs, the pursuing pack limits the options of the deer's movement, and so does the terrain in front of the deer. Suppose the deer sees a tree directly ahead. It has a number of options available: turn to the left, turn to the right, stop, or slam into the tree. Whatever option the deer chooses, the consequences are immediate - the deer either manages to escape for a few more seconds or it is caught and killed by the wolves. If the deer makes enough correct decisions, then it may survive long enough for the wolves to catch another deer and lose interest in our deer.

It is the deer's interaction with the real world that forces it to make decisions, over and over and over again. The deer's mind has functional structures, some preprogrammed by genetics and others learned over the deer's lifetime, and the interaction of these structures - in our example, the structures responsible for sight, smell, heart rate, respiration, and muscular control - which allow the deer to recognize the pursuing pack as a threat, the tree as an obstacle to be avoided, and so on. Good decisions lead to the temporary survival of the animal, and a poor decision leads to the animal's death.

In other words, the real world provides immediate feedback about the effectiveness of decisions. If a decision doesn't kill an animal - suppose it instead receives a minor injury - then that feedback allows the animal to evaluate its decision and make modifications to the connections between functional groups or to the functional groups themselves so that same decision is less likely to be made in the future. Positive feedback - anything that gives the animal pleasure, such as a full belly - also modifies the connections between functional groups in such a way that the structures that led to the decision are reinforced, so that a good decision can be repeated in the future.

Over the animal's lifetime, with the millions of decisions it makes over and over again, and with the real-time feedback provided by the animal's environment evaluating those decisions, the functional structures within its brain and the connections between those structures are constantly modified.

bringing it all together

Let's summarize what we know about intelligence:

1) Intelligence requires the ability to make choices
2) Intelligence is an emergent property of the combination of simpler, unintelligent functional structures
3) the real world provides immediate feedback to evaluate choices; that feedback then changes the unintelligent functional structures and the connections between them

That's it; that's all we need for a working definition of intelligence. With whatever AI we create, we can ask ourselves: is it making choices? are properties emerging from our simpler building blocks? are those choices evaluated and modified by interaction with and feedback from the real world?

In the next installment of Artificial Intelligence 101, we'll look at why we want to create artificial intelligence, and examine past attempts at doing so.

Update July 21, 2011:

The part about choices needs some expansion. Inherent in the ability to make choices is the ability to produce those choices as a synthesis of memory and sensation, and the ability to make predictions about those choices. In the video appended below Jeff Hawkins makes the convincing case that even the sensations themselves are being predicted by the mammalian part of the brain.


The options available to the deer in the example above are being constantly produced and their results predicted; the best prediction becomes the choice, over and over again. Part of the deer's mind is predicting where its foot will make contact with the ground, and if the prediction and reality don't quite match up - say there's a dip in the ground - then new predictions need to be made to match sensation. Prediction is at the foundation of choice and shapes the sensation of reality.